﻿// pro2_1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <stdio.h>
#include <stdlib.h>
#define N 20
int youxian(char c)
{
    if (c == '*' || c == '/')
        return 2;
    if (c == '+' || c == '-')
        return 1;
    return 0;
}

int main()
{
    char stack1[N];                     //操作符栈
    int top_index1 = -1;                //哨兵
    char stack2[N] = { };               //数栈，后缀表达式结果也存于此处  
    int top_index2 = -1;
    char c;
    while (1)
    {
        scanf_s("%c", &c);
        if (c == '\n')
            break;
        else
            if (c >= '0' && c <= '9')       //如果输入的是数字
            {
                top_index2++;
                stack2[top_index2] = c;     //入数栈
            }
            else
                if (c == '(')               //如果输入的是左括号
                {
                    top_index1++;
                    stack1[top_index1] = c; //入操作符栈
                }
                else
                    if (c == ')')           //如果输入的是有括号
                    {
                        while (stack1[top_index1] != '(')       //操作符栈一直出栈直到找到对应的左括号
                        {
                            top_index2++;
                            stack2[top_index2] = stack1[top_index1];    //操作符栈元素出栈进入数栈
                            top_index1--;
                        }
                        top_index1--;       //找到对应的左括号，标记前移
                    }
                    else
                        if (c == '+' || c == '-' || c == '*' || c == '/')   //如果输入的是运算符
                        {
                            if (top_index1 == -1 || youxian(c) > youxian(stack1[top_index1])) //比较优先级
                            {
                                top_index1++;           //若此运算符优先级高于栈顶运算符，运算符入操作符栈
                                stack1[top_index1] = c;
                            }
                            else
                            {
                                while (top_index1 >= 0 && youxian(stack1[top_index1]) >= youxian(c))
                                {
                                    top_index2++;       //若此运算符优先级低于栈顶运算符，操作符栈中元素出栈
                                    stack2[top_index2] = stack1[top_index1];    //进入数栈
                                    top_index1--;
                                }
                                top_index1++;
                                stack1[top_index1] = c; //输入的操作符入栈
                            }
                        }

    }
    while (top_index1 != -1)    //操作符栈非空则输出
    {
        top_index2++;
        stack2[top_index2] = stack1[top_index1];
        top_index1--;
    }
    printf("%s\n",stack2);      //打印出后缀表达式
    int stack3[N];              //直接利用后缀表达式计算
    int top_index3 = -1;
    for (int i = 0; i <= top_index2; i++)
    {
        if (stack2[i] >= '0' && stack2[i] <= '9')
        {
            top_index3++;
            stack3[top_index3] = stack2[i] - 48;    //转码
            continue;
        }
        else
        {
            if (stack2[i] == '+')       //加法
            {
                int t1 = stack3[top_index3];
                int t2 = stack3[top_index3 - 1];
                top_index3--;
                stack3[top_index3] = t1 + t2;   //此数与上一个数相加存到原位置，后面同理
            }
            if (stack2[i] == '-')       //减法
            {
                int t1 = stack3[top_index3];
                int t2 = stack3[top_index3 - 1];
                top_index3--;
                stack3[top_index3] = t2 - t1;
            }
            if (stack2[i] == '*')       //乘法
            {
                int t1 = stack3[top_index3];
                int t2 = stack3[top_index3 - 1];
                top_index3--;
                stack3[top_index3] = t1 * t2;
            }
            if (stack2[i] == '/')       //除法
            {   
                int t1 = stack3[top_index3];
                int t2 = stack3[top_index3 - 1];
                top_index3--;
                stack3[top_index3] = t2 / t1;
            }
        }
    }
    printf("%d", stack3[0]);
}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
